package DataStructure.symbol;

public class OrderSymbolTable<Key extends Comparable<Key>,Value> {
    private Node head;
    private int N;


    public OrderSymbolTable(){
        this.head=new Node(null,null,null);
        this.N=0;
    }



    public int size(){
        return N;
    }

    //往符号表中插入键值对
    public void put(Key key,Value value){
        Node curr=head.next;
        Node pre=head;
        while (curr!=null && key.compareTo(curr.key)>0){
            //变换当前节点和前一个节点
            pre=curr;
            curr=curr.next;
        }
        //如果curr的键和插入的key一样大，则替换，
        if(curr!=null && key.compareTo(curr.key)==0){
            curr.value=value;
        }

        Node newnode = new Node(key, value, curr);
        pre.next=newnode;
        N++;
    }


    //删除键为key的结点，然后删除
    public void delete(Key key){
        Node n=head;//记录每一次遍历的结点
        while (n.next!=null){
            //判断n结点的下一个结点的key是否为key,如果是就删除
            if(n.next.key.equals(key)){
                n.next=n.next.next;
                N--;
                return;
            }
            n=n.next;
        }

    }



    //找到key对应的值
    public Value get(Key key){
        Node n=head;
        while (n.next!=null){
            n=n.next;
            if(n.key.equals(key)){
                return n.value;
            }
        }
        return null;
    }

    private class Node{
        public Key key;
        public Value value;
        public Node next;

        public Node(Key key,Value value,Node next){
            this.key=key;
            this.value=value;
            this.next=next;
        }
    }
}
